/*
============================================================================
 Name        : dd_rbtree.h
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_rbtree.h - header file
============================================================================
*/

#ifndef DD_RBTREE_H
#define DD_RBTREE_H


#include "dd_define.h"


__DD_BEGIN_DECLS


/* 
* The Red-Black Tree Implement 
*/

struct __dd_stack ;

typedef void                        dd_rbtree_key ;
typedef void                        dd_rbtree_value ;
typedef struct __dd_rbtree_node     dd_rbtree_node ;
typedef struct __dd_rbtree_tree     dd_rbtree_tree ;


struct __dd_rbtree_node {

    dd_rbtree_key*   key ;
    dd_rbtree_value* value ;
    dd_rbtree_node*  left_child ;
    dd_rbtree_node*  right_child ;
    DD_INT           color ;
};


struct __dd_rbtree_tree {
    dd_rbtree_node*	    root ;
    struct __dd_stack*  path ;
    DD_INT (*key_compare)(const dd_rbtree_key* key1, const dd_rbtree_key* key2) ;	/* 0: equal ; -1: key1 < key2 ; 1: key1 > key2 */
    void (*key_conflict)(dd_rbtree_key* key_found_conflict, dd_rbtree_value* value_found_conflict, dd_rbtree_key* key_handle, dd_rbtree_value* value_handle) ;
};


dd_rbtree_tree* dd_rbtree_create(
    DD_INT (*key_compare)(const dd_rbtree_key*, const dd_rbtree_key*), 
    void (*key_conflict)(dd_rbtree_key* , dd_rbtree_value*, dd_rbtree_key*, dd_rbtree_value*) 
    ) ;

void dd_rbtree_destroy(dd_rbtree_tree* rbtree) ;

dd_rbtree_value*  dd_rbtree_find(const dd_rbtree_tree* rbtree, dd_rbtree_key* key) ; 

void dd_rbtree_insert(dd_rbtree_tree* rbtree, dd_rbtree_key* key, dd_rbtree_value* value) ;

dd_rbtree_value* dd_rbtree_remove(dd_rbtree_tree* rbtree, dd_rbtree_key* key) ;


#ifdef __DD_UNITTEST

DD_BOOL dd_rbtree_test() ;

#endif

__DD_END_DECLS

#endif  /* DD_RBTREE_H */

/* End of File */
